package com.algrithom.heap;

import java.util.Arrays;

import com.common.constants.NumberConstants;
import com.util.CommonUtil;

/**
 * 最小索引堆
 *
 * @author think
 * @version 1.0.0
 * @since 2020/3/27
 */
public class IndexMinHeap {
    
    /**
     * 索引
     */
    private int[] indexArray;
    
    /**
     * 实际数据
     */
    private int[] data;
    
    private int count;
    
    IndexMinHeap(int len){
        data = new int[len];
        indexArray = new int[len];
    }
    
    public static void main(String[] args){
        IndexMinHeap indexMinHeap = new IndexMinHeap(5);
        int[] array = {4,99,23,64,25};
        Arrays.asList(1,2,3,4,5).forEach(item -> {
            int value = array[item - 1];
            indexMinHeap.insert(item,value);
        });
        System.out.println("索引： " + Arrays.toString(indexMinHeap.indexArray));
        System.out.println("实际数据： " + Arrays.toString(indexMinHeap.data));

        indexMinHeap.delHeapMinData();
        System.out.println("索引： " + Arrays.toString(indexMinHeap.indexArray));
        System.out.println("实际数据： " + Arrays.toString(indexMinHeap.data));
    }
    
    /**
     * 插入元素到最大索引堆
     *
     * @param i 从0 开始计算
     * @param newData 新数据
     */
    public void insert(int i,int newData){
        if (i < 0 || i >= NumberConstants.ONE_HUNDRED) {
            return;
        }
        // 记录数据 pq[] 下标i为t
        data[i - 1] = newData;
        // 记录索引位置 从1开始记录索引
        indexArray[count] = i - 1;
        count = count + 1;
        floatIndex(i - 1);
    }
    
    /**
     * 删除最大的元素 从最大堆取出最大元素
     */
    public void delHeapMinData(){
        CommonUtil.swap(data,indexArray[0],indexArray[count - 1]);
        CommonUtil.swap(indexArray,0,count - 1);
        // 先找到索引,根据索引找到数
        int index = indexArray[count - 1];
        indexArray = Arrays.copyOfRange(indexArray,0,count - 1);
        indexArray = Arrays.stream(indexArray).map(curIndex -> {
            if (curIndex > index) {
                curIndex = curIndex - 1;
            }
            return curIndex;
        }).toArray();
        data = Arrays.stream(data).filter(value -> value != data[index]).toArray();
        count--;
        sinkIndex(0);
    }
    
    public int getMax(){
        return data[indexArray[0]];
    }
    
    /**
     * 从堆中取出最大元素的索引,不删除元素
     *
     * @return 最大元素的索引
     */
    public int getIndexMax(){
        return indexArray[0];
    }
    
    /**
     * 获取最大索引堆索引为i的元素的值
     *
     * @param i 索引
     * @return 实际数据
     */
    public int getCurIndexData(int i){
        return data[indexArray[i]];
    }
    
    /**
     * 堆的上浮，解决子节点比父结点大的问题,少交换，优化堆的上浮过程 比较是比较pq[]的值，交换是交换indexArray[]的值
     *
     * @param k 节点k上浮
     */
    private void floatIndex(int k){
        // 子节点比父结点大
        while (k >= NumberConstants.ZERO && data[indexArray[k / NumberConstants.TWO]] < data[indexArray[k]]) {
            // 父结点移到子节点 子节点暂存 不用每次都去新建一个临时变量来交换
            CommonUtil.swap(indexArray,k,k / NumberConstants.TWO);
            k = k / NumberConstants.TWO;
        }
    }
    
    /**
     * 堆的下沉 父结点小于子节点,将父节点与较大的子节点交换 比较是比较pq[]的值，交换是交换indexArray[]的值
     *
     * @param k 索引
     */
    private void sinkIndex(int k){
        int curIndex = k;
        int curParentDataIndex = indexArray[k];

        int leftIndex = NumberConstants.TWO * k + NumberConstants.ONE;
        int rightIndex = NumberConstants.TWO * k + NumberConstants.TWO;

        if (leftIndex < count && data[indexArray[leftIndex]] > data[curParentDataIndex]) {
            curIndex = leftIndex;
        }
        if (rightIndex < count && data[indexArray[rightIndex]] > data[curParentDataIndex]) {
            curIndex = rightIndex;
        }
        if (curIndex == k) {
            return;
        }
        CommonUtil.swap(indexArray,curIndex,k);
        sinkIndex(curIndex);
    }
}
